﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithm.Middle_18_FourSum
{
    class MainProject
    {
        static void Main(string[] args)
        {
            foreach (var item in FourSum(new int[] { 2, 2, 2, 2, 2 }, 8))
            {
                foreach (var val in item)
                {
                    Console.WriteLine(val);
                }
                Console.WriteLine("----------------------");
            }
            //Console.WriteLine(IsPalindrome(1000021));
            Console.ReadKey();
        }
        public static IList<IList<int>> FourSum(int[] nums, int target)
        {
            //两层循环+排序+双指针

            IList<IList<int>> list = new List<IList<int>>();

            Array.Sort(nums);

            int firstIndex = 0;
            int secondIndex = 0;

            for (int i = 0; i < nums.Length; i++)
            {
                for (int j = i + 1; j < nums.Length; j++)
                {
                    firstIndex = j + 1;
                    secondIndex = nums.Length - 1;
                    if (firstIndex>= nums.Length) break;
                    while (firstIndex < secondIndex)
                    {
                        int sum = nums[i] + nums[j] + nums[firstIndex] + nums[secondIndex];
                        if (sum > target)
                        {
                            secondIndex--;
                        }
                        else if (sum < target)
                        {
                            firstIndex++;
                        }
                        else
                        {
                            if (!list.Any(val=>val[0] == nums[i]&& val[1] == nums[j] && val[2] == nums[firstIndex] && val[3] == nums[secondIndex]))
                            {
                                list.Add(new List<int>() { nums[i], nums[j], nums[firstIndex], nums[secondIndex] });
                            }
                            firstIndex++;
                        }
                    }
                }
            }
            return list;
        }
    }
}
